package structure.stack;

import java.util.*;

/**
 * @Author wangj
 * @Date 2022/4/23 9:37
 * 将中缀表达式转换成后缀表达式，实现计算器
 */
public class SuffixExpression {

    public static void main(String[] args) {
        String expression = "100+((2+3)*4)-5";
        // 将中缀表达式转换成数组
        List<String> list = infillTransferList(expression);
        System.out.printf("infill=%s\n", list.toString());
        // 将中缀表达式转换成后缀表达式
        List<String> suffix = infillTransferSuffix(list);
        System.out.printf("suffix=%s\n", suffix.toString());
        System.out.println(calculation(suffix));
    }

    /**
     * 将表达式转换成list
     *
     * @param string
     * @return
     */
    private static List<String> expressionTransferList(String string) {
        if (string.length() == 0) {
            return null;
        }
        String[] split = string.split("");
        List<String> list = new ArrayList<>(split.length);
        list.addAll(Arrays.asList(split));
        return list;
    }

    /**
     * 将中缀表达式转换成后缀表达式
     *
     * @param infillList
     * @return
     */
    private static List<String> infillTransferSuffix(List<String> infillList) {
        // 存储运算符栈
        Stack<String> operation = new Stack<>();
        // 存储中间结果,由于不存在出栈操作，直接改用数组
        List<String> middleResult = new ArrayList<>();
        // 1，从左到右依次遍历表达式
        for (String str : infillList) {
            // 2,如果是数字，则直接入中间结果栈，
            if (str.matches("\\d+")) {
                middleResult.add(str);
            } else if (str.equals("(")) { // 如果是 ( 直接入栈
                operation.push(str);
            } else if (str.equals(")")) { // 如果是 ） 则将操作符栈弹出添加到中间结果中，直到遇到（ 括号
                while (!operation.peek().equals("(")) {
                    middleResult.add(operation.pop());
                }
                // 注意这里弹出是为了将 （）括号进行消除
                operation.pop();
            } else {
                while (!operation.isEmpty() && (!"(".equals(operation.peek()) && (priority(str) < priority(operation.peek())))){
                    middleResult.add(operation.pop());
                }
                operation.push(str);
                // 3, 操作符 将如下代码优化成上述三行代码
                // 3.1 操作符栈为空,则直接入栈
//                if (operation.empty()) {
//                    operation.push(str);
//                } else if ("(".equals(operation.peek()) || (priority(str) > priority(operation.peek()))) {
//                    // 3.2 如果当前优先级比栈顶的元素高，则直接压入操作符栈
//                    operation.push(str);
//                } else {
//                    // 3.3 如果当前优先级比栈顶元素低，则将操作符栈弹出压入中间结果栈，并接着判断操作符栈顶或空
                        //middleResult.add(operation.pop());
//                    while (operation.empty() || operation.peek().equals("(")) {
//                    }
//                }
            }
        }
        //
        while (!operation.empty()) {
            middleResult.add(operation.pop());
        }
        return middleResult;
    }

    /**
     * 将中缀表达式转换成list。存在多位数
     *
     * @param expression
     * @return
     */
    private static List<String> infillTransferList(String expression) {
        // 用于数字拼接
        String str = "";
        List<String> list = new ArrayList<>();
        //索引
        int i = 0;
        // 每遍历一个字符，赋值给ch
        char ch;
        while (i <= expression.length() - 1) {
            ch = expression.charAt(i);
            if (ch < 48 || ch > 57) {
                list.add(ch + "");
                i++;
            } else {
                str = "";
                while (i < expression.length() && (ch = expression.charAt(i)) >= 48 && (ch = expression.charAt(i)) <= 57) {
                    str += ch;
                    i++;
                }
                list.add(str);
            }
        }
        return list;
    }

    /**
     * 判断操作符的优先级
     *
     * @param operation
     * @return
     */
    private static int priority(String operation) {
        if (operation.equals("*") || operation.equals("/")) {
            return 1;
        } else if (operation.equals("+") || operation.equals("-")) {
            return 0;
        } else {
            throw new RuntimeException("操作符非法");
        }
    }

    /**
     * 根据后缀表达式计算结果
     *
     * @param list
     * @return
     */
    private static int calculation(List<String> list) {
        if (list.size() == 0) {
            return -1;
        }
        Stack<String> stack = new Stack<>();
        for (String str : list) {
            if (str.matches("\\d+")) {
                stack.push(str);
            } else {
                int preNum = Integer.parseInt(stack.pop());
                int afterNum = Integer.parseInt(stack.pop());
                int result = calculation(preNum, afterNum, str);
                stack.push(result + "");
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 根据操作符计算结果
     *
     * @param perNum
     * @param afterNum
     * @param operation
     * @return
     */
    private static int calculation(int perNum, int afterNum, String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = perNum + afterNum;
                break;
            case "-":
                result = afterNum - perNum;
                break;
            case "*":
                result = perNum * afterNum;
                break;
            case "/":
                result = afterNum / perNum;
                break;
        }
        return result;
    }
}
